package com.yangzhe.algorithm.c035;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

// 全O(1)的数据结构
public class Code07_AllO1_LeetCode {

    public static void main(String[] args) {
        AllOne allOne = new AllOne();
        allOne.inc("a");
        allOne.inc("b");
        allOne.inc("b");
        allOne.inc("b");
        allOne.inc("c");
        allOne.inc("c");
        allOne.inc("c");
        allOne.inc("c");
        allOne.inc("c");
        allOne.inc("c");
        allOne.inc("d");
        allOne.inc("d");
        allOne.inc("d");
        allOne.inc("d");
        allOne.inc("d");
        allOne.inc("d");
        allOne.inc("d");
        allOne.inc("d");
        allOne.getMaxKey();
        allOne.getMinKey();
        allOne.inc("b");
        allOne.dec("d");
        allOne.getMaxKey();
        allOne.getMinKey();
    }

    /**
     * 测试链接 : https://leetcode.cn/problems/all-oone-data-structure/
     */
    static class AllOne {

        /**
         * Map 用于O(1)随机查找节点
         */
        private Map<String, Node> map;

        /**
         * 有序的双向链表 用于O(1)查找最大和最小节点
         * 最大节点在tail的上一个
         * 最小节点在head的下一个
         */
        private DoubleLinkedList doubleLinkedList;

        public AllOne() {
            map = new HashMap<>();

            doubleLinkedList = new DoubleLinkedList();
        }

        public void inc(String key) {
            Node cur, node;
            if (!map.containsKey(key)) {
                cur = doubleLinkedList.head;
            } else {
                cur = map.get(key);
                // 如果已经存在，当前节点移动到下一个节点
                cur.keySet.remove(key);
            }

            // 判断下一个节点是否已经建了，如果已经建了则直接把key移到下一个节点，否则要新建一个
            if (cur.next.count == cur.count + 1) {
                node = cur.next;
                node.keySet.add(key);
            } else {
                node = new Node();
                node.count = cur.count + 1;
                node.keySet = new HashSet<>();
                node.keySet.add(key);

                doubleLinkedList.insertNext(cur, node);
            }

            // 如果当前节点已经空了则删除
            if (cur.keySet.isEmpty()) {
                doubleLinkedList.deleteNode(cur);
            }

            map.put(key, node);
        }

        public void dec(String key) {
            if (!map.containsKey(key)) {
                return;
            }

            Node cur = map.get(key);

            if (cur.count - 1 == 0) {
                // 如果是0个，则直接从删除
                map.remove(key);
            } else if (cur.count - 1 == cur.prev.count) {
                // 如果前一个节点已经建了，则直接把key移动过去即可
                cur.prev.keySet.add(key);
                map.put(key, cur.prev);
            } else {
                // 如果没建前一个节点，则还需要新建一个节点
                Node newNode = new Node();
                newNode.keySet = new HashSet<>();
                newNode.keySet.add(key);
                newNode.count = cur.count - 1;

                doubleLinkedList.insertNext(cur.prev, newNode);
                map.put(key, newNode);
            }

            // 不论怎样，当前节点都得把key删掉
            cur.keySet.remove(key);
            if (cur.keySet.isEmpty()) {
                doubleLinkedList.deleteNode(cur);
            }

        }

        public String getMaxKey() {
            return doubleLinkedList.tail.prev.keySet.iterator().next();
        }

        public String getMinKey() {
            return doubleLinkedList.head.next.keySet.iterator().next();
        }

        protected class Node {
            Node prev;
            Node next;
            Set<String> keySet;
            Integer count;

            public Node() {

            }
        }

        protected class DoubleLinkedList {
            public Node head;
            public Node tail;

            /**
             * 初始化 head 和 tail
             * 保证后续插入的节点永远由前序和后续，减少判断的复杂度
             */
            public DoubleLinkedList() {
                head = new Node();
                head.keySet = new HashSet<>();
                head.keySet.add("");
                head.count = 0;

                tail = new Node();
                tail.keySet = new HashSet<>();
                tail.keySet.add("");
                tail.count = Integer.MAX_VALUE;

                head.next = tail;
                tail.prev = head;
            }

            /**
             * 在当前节点之后插入一个节点
             *
             * @param current 当前节点
             * @param newNode 要插入的节点
             */
            public void insertNext(Node current, Node newNode) {
                newNode.next = current.next;
                newNode.prev = current;

                current.next.prev = newNode;
                current.next = newNode;
            }

            public void deleteNode(Node node) {
                node.next.prev = node.prev;
                node.prev.next = node.next;

                node.prev = null;
                node.next = null;
            }
        }
    }

/**
 * Your AllOne object will be instantiated and called as such:
 * AllOne obj = new AllOne();
 * obj.inc(key);
 * obj.dec(key);
 * String param_3 = obj.getMaxKey();
 * String param_4 = obj.getMinKey();
 */

}
